package Wuli_2023;


public class QuickSearch {

    public void quickSort(int nums[], int low, int high) {
        if (low < high) {
            int pirot = partition(nums, low, high);   //基于当前范围划分一次后，当前分割点就确定好了最终位置
            if (low < pirot - 1)       //左右边界一样时，无需排序
                quickSort(nums, low, pirot - 1);
            if (pirot + 1 < high)
                quickSort(nums, pirot + 1, high);
        }
        return;
    }

    /**
     * 将数组起始位置作为pirot
     * 小于pirot的数移到左边，大于pirot移到右边
     *
     * @param low  左边界
     * @param high 有边界
     * @return 返回分隔点最终坐标
     */
    private int partition(int[] nums, int low, int high) {
        int temp = nums[low];  //存储当前pirot值
        //low处位置就会空出来留给小于pirot的数
        while (low < high) {      //当low>=high时，说明所有元素筛选完了一轮
            while (low < high && nums[high] >= temp)          //因为pirot在最左边，从右向左找到第一个小于pirot的数,移到左边
                high--;
            nums[low] = nums[high];           //high处空出来留给大于pirot的数
            while (low < high && nums[low] <= temp)            //从左向右找到第一个大于pirot的数,移到右边
                low++;
            nums[high] = nums[low];           //low处空出来留留给小于pirot的数
        }
        //最终low和high会指向同一位置，分隔点位置会被high处最后一个遍历到的大于pirot的数更新
        nums[low] = temp;
        return low;
    }

}
